package com.nanbei.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @ClassDescription: Catalan 括号生成问题
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/10 15:21
 */
public class GenerateParentheses {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(2));
    }

    public static List<String> generateParenthesis(int n) {
        // 用来存放下边对应的catalan数
        ArrayList<ArrayList<String>> dp = new ArrayList<>();

        dp.add(0, new ArrayList<>(Collections.singleton("")));
        dp.add(1, new ArrayList<>(Collections.singleton("()")));
        // 计算下标为J的Catalan数
        for (int j = 2; j < n + 1; j++) {
            ArrayList<String> list = new ArrayList<>();
            for (int i = 0; i < j; i++) {

                ArrayList<String> aList = dp.get(i);  // 内层要嵌套的括号
                ArrayList<String> bList = dp.get(j - 1 - i); // 外层平级的括号数

                for (String al : aList) {
                    for (String bl : bList) {
                        String s = "(" + al + ")" + bl;
                        list.add(s);
                    }
                }
            }
            dp.add(j, list);
            System.out.println(dp);
        }
        return dp.get(n);
    }
}
